Masala #R111B
Smurflar zinasi
Smurflar bayram kuni umumiy rasmga tushishmoqchi. Ular chapdan o'ngga bir qator bo'lib turishadi.
Rasm chiroyli chiqishi uchun har bir keyingi smurf oldingisidan qat'iy balandroq bo'lishi kerak.
\(i\)-smurfning hozirgi bo'yi \(a_i\). Bir amalda istalgan bitta smurfning bo'yini \(1\) birlikka oshirish mumkin. Bo'yini kamaytirish mumkin emas.
Eng kam nechta amal yordamida smurflar qatorini qat'iy o'suvchi qilish mumkinligini toping.
Kiruvchi ma'lumotlar:
Birinchi qatorda bitta butun son \(t\) beriladi — testlar soni.
Har bir test quyidagi ko'rinishda beriladi:
Birinchi qatorda bitta butun son \(n\) beriladi — smurflar soni.
Ikkinchi qatorda \(n\) ta butun son \(a_1,a_2,\ldots,a_n\) beriladi — smurflarning hozirgi bo'ylari.
Cheklovlar:
\[
1 \le t \le 1000
\]
\[
1 \le n \le 2 \cdot 10^5
\]
\[
0 \le a_i \le 10^9
\]
\[
\sum n \le 2 \cdot 10^5
\]
Chiquvchi ma'lumotlar:
Har bir test uchun alohida qatorda smurflar qatorini qat'iy o'suvchi qilish uchun kerak bo'ladigan eng kam amallar sonini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 5 1 2 3 4 5 3 2 2 2 4 5 4 3 2 1 100 |
0 3 12 0 |
Izoh:
Birinchi testda bo'ylar allaqachon qat'iy o'suvchi.
Ikkinchi testda \([2,2,2]\) qatorini \([2,3,4]\) qilish mumkin. Buning uchun \(0+1+2=3\) amal kerak.
Uchinchi testda \([5,4,3,2]\) qatorini \([5,6,7,8]\) qilish optimal. Jami \(0+2+4+6=12\) amal kerak.
To'rtinchi testda faqat bitta smurf bor, shuning uchun javob \(0\).
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling